간단하게 커널 안의 rbtree를 가져와봤다. 아주 간단하다.
커널 소스의 lib/rbtree.c 를 사용한다. 필요한 파일은 다음과 같다.
/Documentation/rbtree.txt 참고
/lib/rbtree.c
/include/linux/rbtree_augmented.h
** 다음 매크로는 꼭 필요하다. 커널 코드 중 최고로 우아한 것으로 꼽는 list 관련 매크로다.
#define TRUE 1
#define FALSE 0
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
** rbtree.txt 참고하여 인써트, 딜리트, 파인드를 구현한다.
땡. 이제 성능이나 재볼까. 참고로 rbtree.c 의 라이선스는 GPL2다.
* * *
성능을 재봤다. key, value 쌍으로 구성된 map이다.
key는 hash하지 않코 걍 씀. duple이면 걍 에러 뱉음.
for (i = 0; i < 10000000; i++) {
sprintf(temp_buf, "aaa%8ld", i);
sprintf(temp_value, "value%8ld", i);
ez_insert((char *)temp_buf, (char *)temp_value);
}
for (i = 0; i < 10000000; i++) {
sprintf(temp_buf, "aaa%8ld", i);
ez_erase((char *)temp_buf);
}
* 1000만건 삽입 : 8.3초
* 1000만건 삽입 + 삭제 : 13.3초
* 내 머신은 i7, 4코어 (하이퍼쓰레딩 8코어), 16GB, 3.4Ghz, 우분투 리눅스다.
이 정도면 빠른건가? 비교 대상을 또 짜긴 귀찮고... 어떤지 궁금..
이제 최적화를 하면 되는데 malloc 최적화를 하면 된다.
malloc도 사실은 예상 청크 크기 별로 미리 brk를 해 놓는다고 하는데... rbtree를 좀 더 최적화 한다면 slab처럼 아예 메모리 풀을 꾸며놓고 땡겨주는 방법이 있겄다. 좀 지저분해질텐데.. 쓰레드 돌면서 임계점 넘으면 미리 alloc 해두는 방식이 될 듯..
** O2 옵션을 걸어봤다 : 1000만건 삽입 + 삭제 = 11.83초
** O3 옵션을 걸어봤다 : 1000만건 삽입 + 삭제 = 11.85초.. 더 증가함 -_-;;
** key, value를 동적할당 대신 정적할당으로 때려봤다 : +O2 -> 10.82초 .. 미미함..
** O2 옵션 삽입만 : 7.4초
** O2 옵션 검색만 (1000만건 전체 일일이 루핑 검색) : 4.5초결론 :
STL MAP, string, O2 사용 : 13.68초 걸린다.
내부적으로 rbtree라니까 뭐 비슷한 듯...
편의를 위해서라면 STL을 쓰는게 맞겠지만 나는 C가 더 편하다.. -__-;
https://github.com/dawnsea/codes/tree/master/rbtree_test